import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {
    public void bucketSort(int[] nums) {
        int n = nums.length;
        if (n <= 0) return;

        // 创建桶
        List<Integer>[] buckets = new List[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将数组中的元素分布到各个桶中
        for (int num : nums) {
            int bucketIndex = (num - minValue(nums)) / n;
            buckets[bucketIndex].add(num);
        }

        // 对每个桶中的元素进行排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 合并所有桶中的元素
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                nums[index++] = num;
            }
        }
    }

    // 辅助函数：获取数组中的最小值
    private int minValue(int[] nums) {
        int min = nums[0];
        for (int num : nums) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        BucketSort sorter = new BucketSort();
        int[] nums = {4, 2, 5, 1, 3};
        sorter.bucketSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}
